English+GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Quadratischer Rest</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Quadratischer Rest</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">Quadratischer Rest ist ein Begriff aus dem <a href="Teilgebiete_der_Mathematik" title="Teilgebiete der Mathematik">mathematischen Teilgebiet</a> <a href="Zahlentheorie" title="Zahlentheorie">Zahlentheorie</a>. Eine <a href="Ganze_Zahl" title="Ganze Zahl">ganze Zahl</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> heißt quadratischer Rest bezüglich eines <a href="Modulo" class="mw-redirect" title="Modulo">Moduls</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy">, wenn sie zu <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> <a href="Teilerfremdheit" title="Teilerfremdheit">teilerfremd</a> ist und es eine Zahl <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> gibt, für die die <a href="Kongruenz_(Zahlentheorie)" title="Kongruenz (Zahlentheorie)">Kongruenz</a>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\equiv x^{2}{\pmod {m}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e26dd93ceb5282c59b9101947a66cb688ef250d6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.437ex; height:3.176ex;" alt="{\displaystyle a\equiv x^{2}{\pmod {m}}}" loading="lazy"></dd></dl>

gilt, das heißt, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cf0bf28fd28f45d07e1ceb909ce333c18c558c93.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.384ex; height:2.676ex;" alt="{\displaystyle x^{2}}" loading="lazy"> liegen in der gleichen <a href="Restklasse" title="Restklasse">Restklasse</a> modulo <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy">.

Existiert für eine zu <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> <a href="Teilerfremd" class="mw-redirect" title="Teilerfremd">teilerfremde</a> Zahl <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> keine Lösung <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> der obigen Kongruenz, dann nennt man <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> quadratischen Nichtrest modulo <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy">. Zu <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> nicht teilerfremde Zahlen werden nicht klassifiziert, sind also weder quadratische Reste noch quadratische Nichtreste.

<div class="mw-heading mw-heading2"><h2 id="Beispiel">Beispiel</h2></div>

In diesem Beispiel werden die quadratischen Reste und Nichtreste des Moduls 6 ermittelt. Da die Zahlen 0, 2, 3 und 4 nicht teilerfremd zu 6 sind, werden sie nicht klassifiziert. Zur Klassifikation der Zahlen 1 und 5 ist die folgende Tabelle der Quadrate aller Zahlen von 0 bis 5 hilfreich.

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">

</th>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cf0bf28fd28f45d07e1ceb909ce333c18c558c93.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.384ex; height:2.676ex;" alt="{\displaystyle x^{2}}" loading="lazy">

</th>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{2}{\bmod {6}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/952f1c3e719a9843ccc8a769b203dcfa5c167ade.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.228ex; height:2.676ex;" alt="{\displaystyle x^{2}{\bmod {6}}}" loading="lazy">

</th></tr>

<tr>

<td>0

</td></tr>

<tr>

<td>1

</td></tr>

<tr>

<td>4

</td></tr>

<tr>

<td>3

</td></tr>

<tr>

<td>4

</td></tr>

<tr>

<td>1

</td></tr></tbody></table>

Die Zahl 1 findet sich in der rechten Spalte und ist deshalb quadratischer Rest. Die Zahl 5 hingegen ist quadratischer Nichtrest, da sie in der rechten Spalte fehlt.

<div class="mw-heading mw-heading2"><h2 id="Vereinfachte_Berechnung_der_quadratischen_Reste">Vereinfachte Berechnung der quadratischen Reste</h2></div>

Für kleinere Zahlen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> können die quadratischen Reste relativ rasch berechnet werden: Es genügt, die Zahlen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\leq x\leq m/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leq x\leq m/2}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9395a938e35dd253b0eb0a565863f41ea38011bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.054ex; height:2.843ex;" alt="{\displaystyle 0\leq x\leq m/2}" loading="lazy"> zu betrachten, denn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cf0bf28fd28f45d07e1ceb909ce333c18c558c93.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.384ex; height:2.676ex;" alt="{\displaystyle x^{2}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x+k\cdot m)^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x+k\cdot m)^{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/210487df3e1d22d636eb77001099c3a44807ec60.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.964ex; height:3.176ex;" alt="{\displaystyle (x+k\cdot m)^{2}}" loading="lazy"> haben denselben Rest, ebenso <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cf0bf28fd28f45d07e1ceb909ce333c18c558c93.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.384ex; height:2.676ex;" alt="{\displaystyle x^{2}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (-x)^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (-x)^{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9f08e174d0fea99ea342d56d58f01d9c8c9fa742.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.001ex; height:3.176ex;" alt="{\displaystyle (-x)^{2}}" loading="lazy">, also auch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cf0bf28fd28f45d07e1ceb909ce333c18c558c93.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.384ex; height:2.676ex;" alt="{\displaystyle x^{2}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (m-x)^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (m-x)^{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/343fc502511159353b8daf8a5d4702770e41ce93.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.074ex; height:3.176ex;" alt="{\displaystyle (m-x)^{2}}" loading="lazy">.

Die Berechnung wird hier am Beispiel des Moduls <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m=11}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m=11}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bcfdb4444c11806dc1fc6bef70d5db4520d6a280.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.464ex; height:2.176ex;" alt="{\displaystyle m=11}" loading="lazy"> demonstriert.

<pre> 0 mod 11 = 0; 1 mod 11 = 1; 4 mod 11 = 4; 9 mod 11 = 9

16 mod 11 = 5; 25 mod 11 = 3; 36 mod 11 = 3; 49 mod 11 = 5

64 mod 11 = 9; 81 mod 11 = 4; 100 mod 11 = 1; 121 mod 11 = 0

</pre>

Wenn man so weitermacht, wiederholt sich der Zyklus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (0,1,4,9,5,3,3,5,9,4,1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (0,1,4,9,5,3,3,5,9,4,1)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5f78c9a5e9626a8486f8cd8e5be9e92797fe6aad.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.936ex; height:2.843ex;" alt="{\displaystyle (0,1,4,9,5,3,3,5,9,4,1)}" loading="lazy"> immer wieder. Wegen der Symmetriebeziehung <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (m-x)^{2}\equiv x^{2}{\pmod {m}}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (m-x)^{2}\equiv x^{2}{\pmod {m}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fa2013d1cc5dde1824e73f8bd35320571f6f4a70.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.281ex; height:3.176ex;" alt="{\displaystyle (m-x)^{2}\equiv x^{2}{\pmod {m}}}" loading="lazy"> kann man sich auf die Reduktion der Quadratzahlen beschränken, die nicht größer als <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lfloor m/2\rfloor ^{2}=25}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lfloor m/2\rfloor ^{2}=25}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87254e368972e448ac74e77e4dc013bb9dad29fa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.908ex; height:3.176ex;" alt="{\displaystyle \lfloor m/2\rfloor ^{2}=25}" loading="lazy"> sind.

Zur Berechnung der Quadratzahlen kann die Beziehung

<msup>

<mrow>

</mrow>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({n+1}\right)^{2}=n^{2}+2\cdot n+1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/53309f7019f64a9a02a2fa7c324eab2341a56283.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.888ex; height:3.343ex;" alt="{\displaystyle \left({n+1}\right)^{2}=n^{2}+2\cdot n+1}" loading="lazy"></dd></dl>

verwendet werden. Die nächste <a href="Quadratzahl" title="Quadratzahl">Quadratzahl</a> kann also durch Addition von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2n+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2n+1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8ca410f731fe4c7c444330343afb1d1850eadaea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.56ex; height:2.343ex;" alt="{\displaystyle 2n+1}" loading="lazy"> ganz ohne <a href="Multiplikation" title="Multiplikation">Multiplikation</a> berechnet werden. Damit lassen sich die quadratischen Reste für Modul <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m=11}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m=11}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bcfdb4444c11806dc1fc6bef70d5db4520d6a280.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.464ex; height:2.176ex;" alt="{\displaystyle m=11}" loading="lazy"> rasch auch im Kopf berechnen.

Dadurch ergibt sich mit den nachfolgenden Zyklen ein (symmetrisches) Muster:

<pre>mod 2: (0, 1)

mod 3: (0, 1, 1)

mod 4: (0, 1)

mod 5: (0, 1, 4, 4, 1)

mod 6: (0, 1, 4, 3, 4, 1)

mod 7: (0, 1, 4, 2, 2, 4, 1)

mod 8: (0, 1, 4, 1)

mod 9: (0, 1, 4, 0, 7, 7, 0, 4, 1)

mod 10: (0, 1, 4, 9, 6, 5, 6, 9, 4, 1)

mod 11: (0, 1, 4, 9, 5, 3, 3, 5, 9, 4, 1)

mod 12: (0, 1, 4, 9, 4, 1)

mod 13: (0, 1, 4, 9, 3, 12, 10, 10, 12, 3, 9, 4, 1)

mod 14: (0, 1, 4, 9, 2, 11, 8, 7, 8, 11, 2, 9, 4, 1)

mod 15: (0, 1, 4, 9, 1, 10, 6, 4, 4, 6, 10, 1, 9, 4, 1)

mod 16: (0, 1, 4, 9)

mod 17: (0, 1, 4, 9, 16, 8, 2, 15, 13, 13, 15, 2, 8, 16, 9, 4, 1)

mod 18: (0, 1, 4, 9, 16, 7, 0, 13, 10, 9, 10, 13, 0, 7, 16, 9, 4, 1)

mod 19: (0, 1, 4, 9, 16, 6, 17, 11, 7, 5, 5, 7, 11, 17, 6, 16, 9, 4, 1)

mod 20: (0, 1, 4, 9, 16, 5, 16, 9, 4, 1)

…

</pre>

Die Zyklen der durch 4 teilbaren Moduln treten im Muster mehrfach auf.

<div class="mw-heading mw-heading2"><h2 id="Eigenschaften">Eigenschaften</h2></div>

Sind <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"> quadratische Reste modulo <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy">, dann ist auch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ab}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ab}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/49337c5cf256196e2292f7047cb5da68c24ca95d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.227ex; height:2.176ex;" alt="{\displaystyle ab}" loading="lazy"> quadratischer Rest. Dies lässt sich einfach zeigen, indem man beide Zahlen multipliziert: Aus

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\equiv x^{2}{\pmod {m}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e26dd93ceb5282c59b9101947a66cb688ef250d6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.437ex; height:3.176ex;" alt="{\displaystyle a\equiv x^{2}{\pmod {m}}}" loading="lazy"></dd>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b\equiv y^{2}{\pmod {m}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/47fdfbd7f700a7f53f1944e52a91ee13d7b523d8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.035ex; height:3.176ex;" alt="{\displaystyle b\equiv y^{2}{\pmod {m}}}" loading="lazy"></dd></dl>

folgt

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ab\equiv (xy)^{2}{\pmod {m}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7b008061cbe6b10eaeaf3e85ec4e5e8eabb01918.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.399ex; height:3.176ex;" alt="{\displaystyle ab\equiv (xy)^{2}{\pmod {m}}}" loading="lazy"></dd></dl>

sodass auch das Produkt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ab}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ab}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/49337c5cf256196e2292f7047cb5da68c24ca95d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.227ex; height:2.176ex;" alt="{\displaystyle ab}" loading="lazy"> quadratischer Rest ist.

Dank der Teilerfremdheit zu <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> hat <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> ein Inverses. Dieses ist auch ein quadratischer Rest, denn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a^{-1}\equiv (x^{2})^{-1}\equiv (x^{-1})^{2}{\pmod {m}}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{-1}\equiv (x^{2})^{-1}\equiv (x^{-1})^{2}{\pmod {m}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4e5c840dee07aa8c9c81d3d6303ac52e5f8764a8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:34.536ex; height:3.176ex;" alt="{\displaystyle a^{-1}\equiv (x^{2})^{-1}\equiv (x^{-1})^{2}{\pmod {m}}}" loading="lazy">. Das Inverse von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> existiert, denn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\cdot (xa^{-1})\equiv 1{\pmod {m}}}">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\cdot (xa^{-1})\equiv 1{\pmod {m}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/60b4d79e8a242795c310267567bc2352e150c2ca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.696ex; height:3.176ex;" alt="{\displaystyle x\cdot (xa^{-1})\equiv 1{\pmod {m}}}" loading="lazy">.

Da <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\equiv 1^{2}{\pmod {m}}}">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\equiv 1^{2}{\pmod {m}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/496cb7ccdea62b468d459483905f2f44eb3cf8dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.202ex; height:3.176ex;" alt="{\displaystyle 1\equiv 1^{2}{\pmod {m}}}" loading="lazy"> trivialerweise ein Rest ist, erfüllen die quadratischen Reste somit alle Eigenschaften einer <a href="Gruppe_(Mathematik)" title="Gruppe (Mathematik)">Gruppe</a>.

<div class="mw-heading mw-heading2"><h2 id="Legendre-_und_Jacobi-Symbol">Legendre- und Jacobi-Symbol</h2></div>

Für Rechnungen, bei denen man nachweisen will, ob eine Zahl quadratischer Rest ist, stehen zwei Kurzschreibweisen zur Verfügung. Das <a href="Legendre-Symbol" title="Legendre-Symbol">Legendre-Symbol</a> gibt an, ob eine Zahl quadratischer Rest für einen Primzahlmodul ist:

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mstyle>

</mrow>

<mtext> quadratischer Rest modulo </mtext>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mstyle>

</mrow>

<mtext> quadratischer Nichtrest modulo </mtext>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mstyle>

</mrow>

<mtext> ein Vielfaches von </mtext>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}\quad 1,&{\mbox{wenn }}a{\mbox{ quadratischer Rest modulo }}p{\mbox{ ist}}\\-1,&{\mbox{wenn }}a{\mbox{ quadratischer Nichtrest modulo }}p{\mbox{ ist}}\\\quad 0,&{\mbox{wenn }}a{\mbox{ ein Vielfaches von }}p{\mbox{ ist}}\end{cases}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f12a1bb207b49e0a9765e636164009ae47e6affc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.671ex; width:62.167ex; height:8.509ex;" alt="{\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}\quad 1,&{\mbox{wenn }}a{\mbox{ quadratischer Rest modulo }}p{\mbox{ ist}}\\-1,&{\mbox{wenn }}a{\mbox{ quadratischer Nichtrest modulo }}p{\mbox{ ist}}\\\quad 0,&{\mbox{wenn }}a{\mbox{ ein Vielfaches von }}p{\mbox{ ist}}\end{cases}}}" loading="lazy"></dd></dl>

Dieses wird zum <a href="Jacobi-Symbol" title="Jacobi-Symbol">Jacobi-Symbol</a> verallgemeinert, das die Berechnung für beliebige Moduln auf deren Primfaktorzerlegung <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m=p_{1}^{\nu _{1}}\cdot p_{2}^{\nu _{2}}\cdot \ldots \cdot p_{k}^{\nu _{k}}}">

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m=p_{1}^{\nu _{1}}\cdot p_{2}^{\nu _{2}}\cdot \ldots \cdot p_{k}^{\nu _{k}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cc518a478ba94c05fca473082d9c9b5f3ff976f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:22.064ex; height:3.176ex;" alt="{\displaystyle m=p_{1}^{\nu _{1}}\cdot p_{2}^{\nu _{2}}\cdot \ldots \cdot p_{k}^{\nu _{k}}}" loading="lazy"> zurückführt:

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<msup>

<mrow>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msup>

<msup>

<mrow>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msup>

<msup>

<mrow>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({\frac {a}{m}}\right)=\left({\frac {a}{p_{1}}}\right)^{\nu _{1}}\cdot \left({\frac {a}{p_{2}}}\right)^{\nu _{2}}\cdot \ldots \cdot \left({\frac {a}{p_{k}}}\right)^{\nu _{k}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/76c244fca936b6ebbc6bbdaa9a14edf05c6e9ff7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:41.644ex; height:6.176ex;" alt="{\displaystyle \left({\frac {a}{m}}\right)=\left({\frac {a}{p_{1}}}\right)^{\nu _{1}}\cdot \left({\frac {a}{p_{2}}}\right)^{\nu _{2}}\cdot \ldots \cdot \left({\frac {a}{p_{k}}}\right)^{\nu _{k}}}" loading="lazy"></dd></dl>

Da das Jacobi-Symbol für Primzahlmoduln dieselben Werte wie das Legendre-Symbol liefert, ist die Verwendung der gleichen Kurzschreibweise nicht von Nachteil. Als wichtiges Hilfsmittel zur Berechnung des Legendre-Symbols steht das <a href="Quadratisches_Reziprozit%C3%A4tsgesetz" title="Quadratisches Reziprozitätsgesetz">quadratische Reziprozitätsgesetz mit dem ersten und zweiten Ergänzungssatz</a> zur Verfügung. Zu beachten ist aber, dass man am Jacobi-Symbol nicht eindeutig ablesen kann, ob eine Zahl ein quadratischer Rest ist, so ist zum Beispiel <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left({\frac {2}{15}}\right)=1}">

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({\frac {2}{15}}\right)=1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/aa0e7d2e1f0d1acdb8209854d17f89eace7f3bd9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:10.843ex; height:6.176ex;" alt="{\displaystyle \left({\frac {2}{15}}\right)=1}" loading="lazy">, aber 2 kein quadratischer Rest modulo 15.

<div class="mw-heading mw-heading2"><h2 id="Anwendung_in_der_Kryptologie">Anwendung in der Kryptologie</h2></div>

Vor allem in der <a href="Kryptologie" title="Kryptologie">Kryptologie</a> stellt sich vielfach die Aufgabe, für eine vorgegebene Zahl und einen bekannten Modul zu entscheiden, ob diese Zahl für den Modul quadratischer Rest ist. Diese Fragestellung wird als Quadratische-Reste-Problem bezeichnet. Ist der Modul eine <a href="Primzahl" title="Primzahl">Primzahl</a>, so kann dies recht einfach entschieden werden. Andernfalls stellt es sich teilweise recht schwierig dar. Insbesondere besagt die Quadratische-Reste-Annahme, dass es für bestimmte Moduln praktisch nicht möglich ist, diese Frage zu entscheiden.

<div class="mw-heading mw-heading2"><h2 id="Quadratische_Reste_bei_Primzahlmoduln">Quadratische Reste bei Primzahlmoduln</h2></div>

Ist der Modul eine ungerade <a href="Primzahl" title="Primzahl">Primzahl</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy">, so liefert das <a href="Eulersches_Kriterium" class="mw-redirect" title="Eulersches Kriterium">Eulersche Kriterium</a> eine wichtige Aussage über quadratische Reste. Ein zu <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> teilerfremdes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> ist demnach genau dann quadratischer Rest, wenn die folgende Kongruenz gilt:

<msup>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{\frac {p-1}{2}}\equiv 1{\pmod {p}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/61c57298af036683f635d0ccad0739bf49ecca04.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.789ex; height:4.343ex;" alt="{\displaystyle a^{\frac {p-1}{2}}\equiv 1{\pmod {p}}}" loading="lazy"></dd></dl>

Daraus lässt sich herleiten, dass es für einen ungeraden Primzahlmodul <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> genau <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tfrac {p-1}{2}}}">

<mfrac>

<mrow>

</mrow>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tfrac {p-1}{2}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/776dd9c0eaa0ac7a1271fa583ad9bac7b833664c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:3.764ex; height:3.843ex;" alt="{\displaystyle {\tfrac {p-1}{2}}}" loading="lazy"> quadratische Reste und ebenso viele quadratische Nichtreste gibt.

<div class="mw-heading mw-heading3"><h3 id="Der_Fall_von_Primzahlen_und_das_Legendre-Symbol">Der Fall von Primzahlen und das Legendre-Symbol</h3></div>

Im Folgenden sei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m=p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m=p}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fcd0601d3ce5aee187e0b163911064bd17d17770.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.308ex; height:2.009ex;" alt="{\displaystyle m=p}" loading="lazy"> eine Primzahl. Ist weder <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> noch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"> durch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> teilbar, so gibt die folgende Tabelle in Abhängigkeit von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"> an, ob das Produkt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ab}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ab}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/49337c5cf256196e2292f7047cb5da68c24ca95d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.227ex; height:2.176ex;" alt="{\displaystyle ab}" loading="lazy"> quadratischer Rest (R) oder Nichtrest (NR) ist:

<td>

</td>

<td>a R

</td>

<td>a NR

</td></tr>

<tr>

<td>b R

</td>

<td>ab R

</td>

<td>ab NR

</td></tr>

<tr>

<td>b NR

</td>

<td>ab NR

</td>

<td>ab R

</td></tr></tbody></table>

Dies lässt sich auch so formulieren: Für das <a href="Legendre-Symbol" title="Legendre-Symbol">Legendre-Symbol</a> gilt stets

<mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right).}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6c3e2ae81a1d8d995bb13e3cf4164d8f71acb364.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:21.918ex; height:6.176ex;" alt="{\displaystyle \left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right).}" loading="lazy"></dd></dl>

Für ungerade Primzahlen gilt

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<msup>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({\frac {a}{p}}\right)\equiv a^{\frac {p-1}{2}}{\pmod {p}}.}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3798fb50c4a0989ac836b9d7dae1f7f46a1af818.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:24.761ex; height:6.176ex;" alt="{\displaystyle \left({\frac {a}{p}}\right)\equiv a^{\frac {p-1}{2}}{\pmod {p}}.}" loading="lazy"></dd></dl>

Aus dieser Beziehung lässt sich auch unmittelbar die folgende Aussage ablesen:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle -1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/704fb0427140d054dd267925495e78164fee9aac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:2.971ex; height:2.343ex;" alt="{\displaystyle -1}" loading="lazy"> ist quadratischer Rest modulo Primzahlen der Form <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 4k+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 4k+1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/81446e22fb05329fe49c8a552f9145331032564e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.377ex; height:2.343ex;" alt="{\displaystyle 4k+1}" loading="lazy"> und Nichtrest modulo Primzahlen der Form <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 4k+3}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 4k+3}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0378c6656c69e3615e09ebfb030547e3ec56fb63.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.377ex; height:2.343ex;" alt="{\displaystyle 4k+3}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Die_Besonderheit_der_4">Die Besonderheit der 4</h2></div>

Modulo 4 gibt es nur einen quadratischen Rest, nämlich 1. Denn sowohl für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\equiv 1{\pmod {4}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\equiv 1{\pmod {4}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2924ae7ac64db54ea4ac36d0bf7e1d3acc8e7bcc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.502ex; height:2.843ex;" alt="{\displaystyle n\equiv 1{\pmod {4}}}" loading="lazy"> als auch für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\equiv 3{\pmod {4}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\equiv 3{\pmod {4}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bdccf61b17abd089e7089151dfaa1025ac7d92b9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.502ex; height:2.843ex;" alt="{\displaystyle n\equiv 3{\pmod {4}}}" loading="lazy"> ergibt sich <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n^{2}\equiv 1{\pmod {4}}}">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n^{2}\equiv 1{\pmod {4}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a549b495bcfda164d671025367a97b5f6486e6a5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.556ex; height:3.176ex;" alt="{\displaystyle n^{2}\equiv 1{\pmod {4}}}" loading="lazy"> und für gerade Zahlen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> gilt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n^{2}\equiv 0{\pmod {4}}}">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n^{2}\equiv 0{\pmod {4}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e376fc177dcbb9fd89a997566056f7098fd4af16.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.556ex; height:3.176ex;" alt="{\displaystyle n^{2}\equiv 0{\pmod {4}}}" loading="lazy">. 3 ist demzufolge quadratischer Nichtrest, was bedeutet, dass keine Quadratzahl modulo 4 den Rest 3 lässt. Die ungeraden Primzahlen (also alle außer 2) lassen sich daher in zwei Gruppen einteilen:

<ul><li>Primzahlen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy">, für die <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p\equiv 1{\pmod {4}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p\equiv 1{\pmod {4}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/125d70c2c8848e96954eddfc7f9283ec4f676ed7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:16.366ex; height:2.843ex;" alt="{\displaystyle p\equiv 1{\pmod {4}}}" loading="lazy"> gilt: Für sie existieren Quadratzahlen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n^{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ac9810bbdafe4a6a8061338db0f74e25b7952620.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.449ex; height:2.676ex;" alt="{\displaystyle n^{2}}" loading="lazy"> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n^{2}\equiv (p-1){\pmod {p}}}">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n^{2}\equiv (p-1){\pmod {p}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/dc98387f572145be7fc6745792900434556e0915.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.382ex; height:3.176ex;" alt="{\displaystyle n^{2}\equiv (p-1){\pmod {p}}}" loading="lazy">. Für die Primzahlen dieser Gruppe gilt:</li></ul>

<msup>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (p-1)^{\frac {p-1}{2}}\equiv 1{\pmod {p}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8e8834c7b0b7a6c3dfaaa3cb9d276b359e3b86fb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.541ex; height:4.343ex;" alt="{\displaystyle (p-1)^{\frac {p-1}{2}}\equiv 1{\pmod {p}}}" loading="lazy"></dd></dl></dd>

<dd>Mit dem <a href="Legendre-Symbol" title="Legendre-Symbol">Legendre-Symbol</a> kann man dafür auch

<mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({\frac {p-1}{p}}\right)=1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d9222bd072900229d8ed2eb34a7fd4e6d852cd79.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:13.691ex; height:6.176ex;" alt="{\displaystyle \left({\frac {p-1}{p}}\right)=1}" loading="lazy"></dd></dl></dd>

<dd>schreiben oder kürzer:

<mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({\frac {-1}{p}}\right)=1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a7493522968141c7c56fd8141542f8a17a318b8e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:11.489ex; height:6.176ex;" alt="{\displaystyle \left({\frac {-1}{p}}\right)=1}" loading="lazy"></dd></dl></dd></dl>

<ul><li>Primzahlen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/06809d64fa7c817ffc7e323f85997f783dbdf71d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}" loading="lazy">, für die <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q\equiv 3{\pmod {4}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q\equiv 3{\pmod {4}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7afd24fc810315cb1190a9c7110155e6ace33447.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.177ex; height:2.843ex;" alt="{\displaystyle q\equiv 3{\pmod {4}}}" loading="lazy"> gilt: Für sie existieren keine Quadratzahlen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n^{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ac9810bbdafe4a6a8061338db0f74e25b7952620.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.449ex; height:2.676ex;" alt="{\displaystyle n^{2}}" loading="lazy"> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n^{2}\equiv (q-1){\pmod {q}}}">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n^{2}\equiv (q-1){\pmod {q}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3a3b751aef70157f14583155e096d5a61c08c9b2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.183ex; height:3.176ex;" alt="{\displaystyle n^{2}\equiv (q-1){\pmod {q}}}" loading="lazy">. Für die Primzahlen dieser Gruppe gilt:</li></ul>

<msup>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (q-1)^{\frac {q-1}{2}}\equiv (q-1){\pmod {q}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/47f00449c454b152fa3f709e836af64d8bc039ac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.003ex; height:4.343ex;" alt="{\displaystyle (q-1)^{\frac {q-1}{2}}\equiv (q-1){\pmod {q}}}" loading="lazy"></dd>

<mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({\frac {q-1}{q}}\right)=-1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/22a992a3e606c67faf4a6c93963b91f78a17fdee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:15.399ex; height:6.176ex;" alt="{\displaystyle \left({\frac {q-1}{q}}\right)=-1}" loading="lazy"></dd>

<mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({\frac {-1}{q}}\right)=-1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b034b850050998767e6c9b2fe5b4c2befd7dce67.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:13.297ex; height:6.176ex;" alt="{\displaystyle \left({\frac {-1}{q}}\right)=-1}" loading="lazy"></dd></dl></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li><a href="Peter_Bundschuh" title="Peter Bundschuh">Peter Bundschuh</a>: Einführung in die Zahlentheorie. 5. Auflage. Springer, 2002, ISBN 3-540-43579-4, S. 124 und 127–147.</li></ul></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-02-06" href="https://de.wikipedia.org/wiki/?title=Quadratischer_Rest&oldid=253032185">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>